1. Field of the Invention
The present invention relates to a method and a system for determining a successful bidder in an auction for products offered for sale and for which buyers submit bids, such as auction or competitive bids, that each include a product and a desired volume and an evaluation price. In particular, the present invention pertains to a technique for employing a practical number of calculations to make a determination that generally, when large volumes of product sets of multiple types are bid on, requires a huge number of calculations.
2. Related Art
Spurred by the development and generalization of Internet techniques that serve as background, electronic commerce and electronic auctions have relatively recently become popular.
For such an auction, a process is performed during which collected bids are sorted through to determine which bidder or bidders have submitted successful bids for the purchase of goods. Generally, the determinations involved are based on the selection of a bid or bids that provide a seller the maximum profit.
When a product targeted for trade is the only one of its type, the successful bidder is the buyer whose bid represents a cost evaluation higher than all others. For example, if a single jar is put up for auction, the buyer who offers the highest price for the jar will be the successful bidder.
For an auction or for bidding performed for business to business transactions, products tend to be offered and purchased in bulk. For example, assume a transaction wherein a vendor having multiple computers in stock accepts, from multiple buyers, bids of “600,000 yen for five computer units (120,000 yen per unit)”. In this case, a set of bids is selected wherein the total evaluation price (the price obtained by multiplying the evaluation price for one unit by the number of units) for the individual bids is the maximum.
It should be noted, however, that a condition must be satisfied whereof the volume of the goods involved in the transaction (the total number of units covered by the selected bids) will not exceed the volume available for the transaction (the stock count). That is, the set of bids that provide the maximum gain with the least dead stock is selected, and the companies who submitted these bids are the successful bidders. This problem is equivalent to a well known knapsack problem, and the optimum solution can be obtained by dynamic programming.
As is well known, dynamic programming is an optimum programming method that when used to solve N one-dimensional problems provides for an N-dimensional multi-stage decision problem to be replaced by a functional recursive equation, based on the principle of optimality. The above problem is represented as an established form according to which, for example, a subset {bk} is calculated that maximizes Σrkek under a condition wherein Σrk≦s, when n (=|B|) bids (in the above example, the purchase orders for computers) are provided as a set B={b1, b2, . . . , bk, . . . , bn}. It should be noted that rk denotes the number of products ordered in bid bk, ek denotes the evaluation price for one product in bid bk, s denotes the count of the products in stock, and rk denotes a non-negative integer.
The algorithm used for this problem is as follows. First, the evaluation value array V(k,j) is defined in the (n+1)×(s+1) space, with k denoting an integer of 1≦k≦n+1, and j, an integer of 0≦j≦s.
As the initial step, the following equations are calculated.V(|B|+i,j):=0 for all 0≦j≦s V(k,s):=V(|B|+1,s) for all 1≦k≦|B|  [Equation 11]
Further, the following recursive equation is defined.V(k,j):=max{V(k+1,j),V(k,j+1),V(k+1,j+rk)+rkek}  [Equation 12]
It should be noted that max{a,b,c} is a function for providing the maximum value selected from among those represented by a, b and c.
Then, the recursive equation is calculated, in the descending order, for k from |B| to 1 and for j from s−1 to 0. When j+rk exceeds s, the value of V(k+1,j+rk)+rkek is not selected.
When the calculations for the recursive equation are continued until k=1 and j=0, the value substituted into V(1,0) indicates the maximum gain. Then, when the back tracking is performed along the route by which V(k, j) is reached from the maximum value (=V(1,0)) to 0 (=V(|B|+1, s)), the selected bit bkcan be identified.
That is, when there is only one type of product, a bid designating more than one unit and evaluation price can be optimally selected (determined) using dynamic programming. In the above process, the number of required calculations is O (|B|)
When each bid submitted must be limited to a single type of product, even when multiple types of products are offered for sale, if no restriction is imposed on the submission of bids for different product types, substantially, this is the same as when an auction is separately performed for each product type. Thus, the bids are sorted for each product, and the above method can be used for each product to determine a successful bidder.